package done.easy_501_600;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static java.lang.Math.max;

/**
 * 543. Diameter of Binary Tree 二叉树的直径
 * <p>
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任
 * 意两个结点路径长度中的最大值。这条路径可能穿过根结点。
 * 示例 :
 * 给定二叉树
 * <p>
 * 1
 * / \
 * 2   3
 * / \
 * 4   5
 * 返回 3 , 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 * <p>
 * 注意：两结点之间的路径长度是以它们之间边的数目表示。
 *
 * @author wangxiaozhe
 */
@Slf4j
public class DiameterOfBinaryTree {

    @SuppressWarnings("all")
    public int diameterOfBinaryTree(TreeNode root) {
        // 190329 first
        // 190408 second 用了两次解决
        return 0;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        4, 5), 3);
        log.info("result:{}", diameterOfBinaryTree(root));
    }
}








































/*
public int diameterOfBinaryTree(TreeNode root) {
    int[] res = new int[1];

    deep(root, res);

    return res[0];
}

@SuppressWarnings("all")
public int deep(TreeNode root,int[] res) {
    if (root == null) {
        return 0;
    }

    // 左子树直径
    int left =
            root.left == null ? 0 : deep(root.left, res);  //左右子树为空，返回0，否则返回值加一

    // 右子树直径
    int right =
            root.right == null ? 0 : deep(root.right, res);

    // 缓存的直径 与两个和对比取最大
    res[0] = max(res[0], left + right); //以root为根节点的直径为left + right

    return max(left, right) + 1;
}
*/
